The present exemplary embodiment relates to lean manufacturing and to Lean Document Production (LDP). It finds particular application in conjunction with document printing operations using process friendly cells and will be described with particular reference thereto. However, it is to be appreciated that the present exemplary embodiment is also amenable to other like applications.
Conventional print shops are organized in a manner that is functionally independent of the print jobs, the print job mix, and the total volume of print jobs passing through the system.
Thus, traditionally, a print shop would arrange its equipment such that all the printers are clustered in a “printers-only” area, all the inserters in an “inserters-only” area, and so on. The implication of this is that printers are only close to other printers and inserters only close to other inserters, effectively creating a separation between different types of machines that must be closely involved in order to get a single manufacturing job done. As a result, work in progress (WIP) in traditional print shops can be very high and, at the same time, the average job turn-around time is elongated. The LDP solution recognizes this “friction” in the document production process, and re-organizes the print shop layout to create process-friendly mini-shops called “cells” that eliminate much of these inefficiencies.
Particular examples of Lean Document Production (LDP) technology have been described, in U.S. Patent Application No. 20070204226, by Hindi et al., entitled, “System And Method For Manufacturing System Design And Shop Scheduling Using Network Flow Modeling”; U.S. Patent Application No. 20040225394, by Fromherz et al., entitled, “Predictive And Preemptive Planning And Scheduling For Different Job Priorities System And Method”; U.S. Patent Application Publication No. 20080144084, by Rai, entitled, “Method For Managing One Or More Print Processing Queues”; U.S. Pat. No. 7,065,567, by Squires et al., entitled, “Production Server For Automated Control Of Production Document”; U.S. Pat. No. 7,079,266, by Rai, et al., entitled, “Printshop Resource Optimization Via The Use Of Autonomous Cells”; and U.S. Pat. No. 7,051,328, by Rai et al., entitled, “Production Server Architecture And Methods For Automated Control Of Production Document Management”. While the LDP solution contains an array of innovations to make document production a “lean” process, the concept of cellular manufacturing remains at the heart of this technology, and this has created a number of technical challenges, the most notable of which is how to schedule jobs efficiently in a manufacturing environment that is organized around the notion of cells. Besides the emergence of cells as new scheduling entities, there are a number of other issues that pose additional challenges to schedulers employed in LDP systems.
One issue is the heavy-tailed job size distribution, which refers to the fact that print jobs (especially the ones found in large print shops) vary significantly in sizes such that their distributions can no longer be sufficiently characterized by any “textbook” distributions (such as normal or exponential distributions) that have a finite variance. Given that many scheduling algorithms and systems assume quite the opposite (i.e., only dealing with distributions that are not heavy-tailed), new schedulers are needed to meet this challenge. Another issue is sequence-dependent setup costs, which refer to the fact that the time it takes to setup a job on a machine depends on the last job the same machine processed. For instance, if two consecutive jobs on the same machine share the same setup, then switching from one job to the other can be done much faster than if the machine is being asked to perform a different job. One example would be if a printer is printing envelopes of a certain size and the next job uses the same size envelopes. In this situation, the setup time for the next job would be faster than if the next job required different sized envelopes.
Existing schedulers take the form of a two-tiered scheduling approach in which a job is first assigned to a cell (or a sequence of cells if needed) by a shop-level scheduler, and since each cell has its own job queue, once a job is assigned to some cell, it is permanently bound to that cell until the job steps within the cell are finished. This strategy works well if the shop-level scheduler can accurately predict the workload of each cell at any moment and compute a mapping from jobs to cells in a way that keeps the utilization level of each cell as high (or evenly distributed) as possible. With current schedulers, however, there are situations in which this can be difficult to achieve. The reason is that the shop-level scheduler does not take into account detailed scheduling constraints within each cell while making its decisions. Factors such as the specific arrival and due dates of a job, the sequence-dependent setup costs, and the number of jobs with similar due dates scheduled in a single cell are not addressed by the shop-level scheduler. Obviously, all these unaddressed factors can (and usually do) contribute to the workload of a cell at any given time. Thus, any such fixed mapping from jobs to cells tends to overload some cells while leaving others idle from time to time.
Another area where improvements of existing LDP systems would be beneficial is in the area of “batch-splitting”, which is a throughput-improvement strategy for handling large jobs in LDP systems. Batch-splitting chops a long job into a number of smaller units called “batches.” At times batches may also be referred to as sub-jobs. The idea is to eliminate downstream waiting as soon as a small fraction of a long job is ready to flow through the system. Examples of systems employing the batch-splitting concepts are described, for example, in U.S. Patent Application Publications: U.S. Patent Application Publication No. 20070236724, by Rai et al., entitled, “Print Job Management System”; U.S. Patent Application Publication No. 20070247657, by Zhang et al., entitled, “Print Job Management System”; and, U.S. Patent Application Publication No. 20070247659, by Zhang, entitled, “Print Job Management System”.
In these patent applications jobs are split at the shop level using a statistical method and the split jobs are routed to cells. This makes it hard for a cell-level scheduler to focus on jobs that still have a chance to be on-time by delaying the processing of batches that belong to already-late jobs. It is noted this problem is unlikely to be solved by assigning each batch a carefully-chosen fixed priority number when batch-splitting is done, because it is usually too early to tell if the job as a whole is going to be late or not.
The present application addresses these and other issues.